A data storage device with a media cache and a next-level data storage tier optimized for sequential reads, such as a device using shingled magnetic recording (SMR), may experience constrained throughput if the data to be read by a host is fragmented on the media cache or fragmented between the media cache and the main data store. “Cleaning” the media cache based on a first-in-first-out manner may be inefficient computationally and/or in terms of power consumption.